⟸ Go Back ⟸

Exercise 4 (Homework 2).

(regular languages, Kleene star, minimization of DFAs)

Kleene star of a regular language is regular

1. Explicitly construct the minimum DFA for the language L^*, where

   1. L=\{xay\in\{a,b\}^*\mid |y|=1\}.
   2. L=\{xaby\in\{a,b\}^*\mid |y|=1\}.
   3. L=\{axaby\in\{a,b\}^*\mid |y|=1\}.

   Construct the minimum DFA recognizing L. From that DFA, construct a \lambda-NFA A recognizing the language L^*. Using the power-set construction, make A deterministic and then minimize the DFA obtained.

2. Given a DFA A as input, what is the cost of computing a DFA for L(A)^*?